package com.liuyfly.leetcode.questions;

import com.liuyfly.leetcode.util.LeetcodeUtil;
import lombok.extern.slf4j.Slf4j;

@Slf4j
public class Question0041 {
    /**给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

     请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
      

     示例 1：

     输入：nums = [1,2,0]
     输出：3
     示例 2：

     输入：nums = [3,4,-1,1]
     输出：2
     示例 3：

     输入：nums = [7,8,9,11,12]
     输出：1

     来源：力扣（LeetCode）
     链接：https://leetcode.cn/problems/first-missing-positive
     著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */
    public static int firstMissingPositive(int[] nums) {
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            if (nums[i] <= 0) {
                nums[i] = length + 1;
            }
        }
        LeetcodeUtil.printArray(nums);
        for (int i = 0; i < length; i++) {
            int temp = nums[i];
            if (temp<0){
                temp = -temp;
            }
            if (temp <= length && temp>0&&nums[temp-1]>0) {
                nums[temp-1] = -1 * nums[temp-1];
            }
        }
        LeetcodeUtil.printArray(nums);
        for (int i = 0; i < length; i++) {
            if (nums[i] >= 0) {
                return i + 1;
            }
        }
        LeetcodeUtil.printArray(nums);
        return length+1;
    }

    public static void main(String[] args) {
        int[] array = {1,2,0};
//        int[] array = {7,8,9,11};
//        int[] array = {1,1};
//        int[] array = {0,1,2};
        int result = firstMissingPositive(array);
        log.info("result:{}", result);
    }
}
